package gmat.test


public class ID3wo{
	final static inf = Double.POSITIVE_INFINITY
	final static eps = Double.MIN_VALUE
	
	def useTree(List patterns, List indices, Tree tree, int nBins, List uc){
		List targets = []
		int vsize = patterns.first().size()
		vsize.times({ targets += 0 })
		
		if(indices.isEmpty()){
			return targets
		}
		
		if(patterns.size() == 1 || tree.split_dim == 0){
			def rand = new Random()
			
			for(i in 0..nBins-1){
				List id = indices.findAll({ patterns[it % vsize][(int)(it / vsize)] == i })
				if(!id.isEmpty()){
					if(tree.child[i] != inf){
						if(id.size() == 1){
							targets[id.first()] = tree.child[i]
						} else{
							id.each({ targets[it] = tree.child[i] })
						}
					} else{
						if(id.size() == 1){
							targets[id.first()] = uc[rand(uc.size())]
						} else{
							id.each({ targets[it] = uc[rand(uc.size())] })
						}
					}
				}
			}
			return targets
		}
		
		def dim = tree.split_dim
		def dims = (0..patterns.size()-1).toList - dim
		
		for(i in 0..nBins-1){
			List id = indices.findAll({ patterns[dim][it] == i })
			List summand = useTree(patterns[dims], id, tree.child[i], nBins, uc)
			(0..targets.size()-1).each({ targets[it] = targets[it] + summand[it] })
		}
		return targets
	}
	
	def makeTree(List patterns, List targets, int incNode, int nBins){
		Tree tree
		int ni = patterns.size()
		int l = patterns.first().size()
		List uc = targets.flatten().unique()
		
		if(ni == 1 || incNode > l){
			for(i in 0..nBins-1){
				tree.split_dim = 0
				if(!targets.flatten().isEmpty()){
					List indices = []
					int hsize = targets.size()
					for(row in 0..targets.size()-1){
						List id = targets[row].findIndexValues({ it == i })
						indices += id.collect({ row * hsize + it })
					}
					if(!indices.isEmpty()){
						List filter = []
						int vsize = targets.first().size()
						indices.each({ filter += targets[it % vsize][(int)(it / vsize)] })
						if(filter.unique().size() == 1){
							tree.child[i] = targets[indices.first()]
						} else{
							List hist = []
							uc.each({ hist += filter.count(it) })
							tree.child[i] = uc[hist.indexOf(hist.max())]
						}
					} else{
						tree.child[i] = inf
					}
				} else{
					tree.child[i] = inf
				}
			}
			return tree
		}
		
		def pNode = []
		List flat = targets.flatten()
		uc.each({ pNode += flat.count(it) / l })
		def iNode = pNode.collect({ Math.log(it) * it }).sum() * -1/Math.log(2)
		
		List deltaIb = []
		List p = []
		uc.each({ p.add([]) })
		
		for(i in 0..ni-1){
			for(j in 0..uc.size()-1){
				for(k in 0..nBins-1){
					p[j][k] = patterns[i][flat.findIndexValues({ it == uc[j] })].count(k)
				}
			}
			List pK = []
			p.each({ pK += it.sum() })
			p = p.collect({ row -> row.collect({ el -> el / l }) })
			def sum = pK.sum()
			pK = pK.collect({ it / sum })
			List lp = []
			for(x in 0..p.size()-1){
				lp.add([])
				p[x].each({ lp[x] += Math.log(it + eps) * it })
			}
			List info = []
			lp.each({ info += it.sum() * -1/Math.log(2) })
			def pKinfoSum = 0
			(0..pK.size()-1).each({ pKisum += pK[it] * info[it] })
			def pKlogSum = 0
			pK.each({ pKlogSum += Math.log(it + eps) * it })
			deltaIb[i] = -Math.log(2) * (iNode - pKinfoSum) / pKlogSum
		}
		
		def dim = deltaIb.findIndexOf({ it == deltaIb.max() })
		
		tree.split_dim = dim
		def dims = (0..ni-1).toList() - dim
		for(i in 0..nBins-1){
			def indices = patterns[dim].findIndexValues({ it == i })
			List filter = []
			int vsize = targets.first().size()
			indices.each({ filter += targets[it % vsize][(int)(it / vsize)] })
			tree.child[i] = makeTree(patterns[dims][indices], filter, incNode, nBins)
		}
		
		return tree
	}
}
